home *** CD-ROM | disk | FTP | other *** search
- Path: seismo!uunet!rs
- From: rs@uunet.UU.NET (Rich Salz)
- Newsgroups: comp.sources.unix
- Subject: v10i011: Crypt Breaker's Workbench, Part11/11
- Message-ID: <413@uunet.UU.NET>
- Date: 21 Jun 87 16:37:13 GMT
- Organization: UUNET Communications Services, Arlington, VA
- Lines: 1089
- Approved: rs@uunet.uu.net
-
- Submitted by: Robert W. Baldwin <BALDWIN@XX.LCS.MIT.EDU>
- Mod.sources: Volume 10, Issue 11
- Archive-name: cbw/Part11
-
- #! /bin/sh
- # This is a shell archive. Remove anything before this line, then unpack
- # it by saving it into a file and typing "sh file". To overwrite existing
- # files, type "sh file -c". You can also feed this as standard input via
- # unshar, or by typing "sh <file", e.g.. If this archive is complete, you
- # will see the following message at the end:
- # "End of archive 11 (of 11)."
- # Contents: cbw.doc
- # Wrapped by rs@uunet on Wed Jun 17 18:17:34 1987
- PATH=/bin:/usr/bin:/usr/ucb ; export PATH
- if test -f cbw.doc -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"cbw.doc\"
- else
- echo shar: Extracting \"cbw.doc\" \(51998 characters\)
- sed "s/^X//" >cbw.doc <<'END_OF_cbw.doc'
- X
- X
- X
- X
- X
- X
- X
- X CRYPT BREAKERS WORKBENCH
- X
- X USERS MANUAL
- X
- X
- X
- X
- X
- X
- X
- X
- X Robert W. Baldwin
- X baldwin@xx.lcs.mit.edu
- X mit-eddie!baldwin
- X October, 1986
- X
- XOverview
- X The Crypt Breakers' Workbench (CBW) is an interactive multi-window system
- Xfor mounting a cipher-text only attack on a file encrypted by the Unix crypt
- Xcommand. CBW is a workbench in the sense that it provides the user with an
- Xintegrated set of tools that simplify the initial, middle and final portions of
- Xthe decryption process. A user interacts with the workbench by choosing tools
- Xand setting parameters. CBW carries out the work and displays the results. A
- Xmoderately experienced user of CBW can easily decrypt both long and short
- Xmessages when bigram statistics are known for the message space. The basic
- Xcryptanalytic techniques used by CBW are described in a paper by Reeds and
- XWeinberger that appeared in the October 1984 issue of the ATT Bell Laboratories
- XTechnical Journal. This manual explains the capabilities and operating
- Xprocedures of CBW.
- X
- X1. Introduction to the Workbench
- X A workbench is a place where a craftsman can quickly and comfortably carry
- Xout a wide range of tasks. The ease of performing tasks comes from the range
- Xof tools present on the workbench and the experience of the craftsman. Each
- Xtool has its strengths and limitations, but the craftsman can select the best
- Xtool for the job at hand. The workbench is not a static thing. Often the
- Xcraftsman builds a jig that is tailored to a particular problem. Some jigs are
- Xlater discarded while others become permanent fixtures of the workbench. It is
- Xin this sense of the term workbench that CBW is a workbench for breaking the
- XUnix crypt cipher.
- X
- X CBW has evolved over the past two years, and it will continue to evolve as
- Xthe process of decrypting Unix files becomes better understood. Already I can
- Xthink of commands that I want to add to speed up the end-game of the decryption
- Xprocess. It is being released in its current form to allow others to play with
- Xit and add their own ideas.
- X
- X One goal of releasing CBW is to discourage people from using the Unix
- Xcrypt command for sensitive information. Crypt was never intended to be a
- Xhighly secure cipher. It's primary advantage has been its speed, which made it
- Xsuitable for integration into a wide range of application programs. The CBW
- Xprogram simply points out how easy the cipher is to break using the ideas
- Xdescribed by Reeds and Weinberger in the October 1984 issue of the ATT Bell
- XLabs Technical Journal. As those authors suggested, if you must use crypt, you
- Xshould run compress on the file before encrypting it.
- X
- X2. Key Space Attack
- X The basic metaphor of CBW is that the computer knows several message-space
- Xsearching strategies, and the user decides which strategy to try next. The
- Xprogram takes on the burden of carrying out the strategy, but it is up to the
- Xuser to choose the strategy and to set the necessary parameters (e.g., how
- Xclose a scoring statistic has to be to its expected value before the program
- Xwill accept a guess). When a strategy completes, its results are displayed.
- XAn important feature of the program is that the results are displayed in a
- Xmanner that makes it easy for the user to decide what to do next. Further, it
- Xeasy to carry out decisions such as accepting the outcome as is, accepting it
- Xwith minor changes, or starting over with a different strategy or a different
- Xparameter setting.
- X
- X To use CBW it is necessary to know a few facts about the underlying cipher
- Xsystem, in this case the Unix crypt program. The primary fact to know is that
- Xthe job of deciphering a file can be broken down into several smaller jobs.
- XThe ciphertext being decoded can be divided into blocks of 256 characters, and
- Xeach block can be decoded separately.
- X
- X Each block is encrypted using a relatively simple cipher system, but the
- Xkey to this simple system changes at the end of each block. Effectively, each
- Xblock is encrypted by a single rotor enigma system. The rotor has 256
- Xpositions to handle full eight-bit bytes, and this leads to the number of
- Xcharacters in each block. CBW represents the wiring for each block's rotor by
- Xa permutation matrix.
- X
- X Once several blocks are decoded (or mostly decoded), it becomes possible
- Xto determine how the key changes after each block. The key change is expressed
- Xas a permutation matrix called Zee. Typically one needs to solve four or five
- Xblocks (about 1000 characters), before it is possible to automatically compute
- XZee and solve the rest of the file. For short messages there is no need to
- Xcompute Zee.
- X
- X After the inter-block relationship has been determined, the program,
- Xzeecode, can be used to decipher the whole file. The program zeecode looks at
- Xthe save-file produced by CBW to get the information it needs to decode an
- Xentire file.
- X
- X3. Files, Terminals and Shell Variables
- X This documentation assumes that the code, source, and datafiles are kept
- Xin a directory called /projects/Ecrypt, but these files could be placed
- Xanywhere.
- X
- X The most important files are the program itself, and the files that
- Xcontain the English language statistics. The program is called 'cbw'. The
- Xstatistics files are 'mss.stats', 'mss-bigram.stats', and 'trigram.stats'. For
- Xthe probable word guessing command there are files like 'common.words'.
- X
- X To make it easy for users to provide their own statistics files, cbw uses
- Xthe shell variables LETTERSTATS, BIGRAMSTATS, and TRIGRAMSTATS to access these
- Xfiles. The variable DICTIONARY identifies a file of words for the
- Xlookup-pattern command (one word per line). These shell variables must be set
- Xto the full pathnames for the desired files. The file stats.slice defines all
- Xof these variables. Your .login file should contain a line like:
- X
- X source /projects/Ecrypt/stats.slice
- X
- X The main input to cbw is a ciphertext file, and the main output is a save
- Xfile that specifies how the ciphertext can be decoded. The program 'zeecode'
- Xuses CBW's save file to decode the ciphertext file. The ciphertext file for
- Xcbw is assumed to have a name like 'fileroot.cipher'. The output of cbw is
- Xstored in the file named 'fileroot.perm'. The '.perm' stands for permutation.
- X
- X
- X
- X3.1. Terminal compatibility
- X CBW is designed to run on any display terminal. To run on a particular
- Xterminal CBW must be able to generate graphic characters on that terminal and
- Xbe able to recognize the escape sequences sent by that terminal's function keys
- X(e.g., the arrow keys). CBW adapts to different terminals by examining shell
- Xvariables (TERM, GRAPHICSMAP, and KEYMAP), the termcap entry, and compiled in
- Xdefaults. It builds a keystroke map and a graphics symbol map which translate
- Xbetween arbitrarily long sequences of ascii characters and the internal
- Xrepresentation for keystroke commands and graphic symbols. The rest of this
- Xdocument will describe the action of keys, but the reader should remember that
- Xthe binding between commands and keys can be changed.
- X
- X You should be able to use CBW without understanding the details of
- Xterminal handling, but for completeness, those details are presented in the
- Xappendix. You will need to be sure that the shell variable TERM identifies the
- Xkind of terminal you are using. You should also be able to find a shell script
- Xthat will set up the graphics map for your terminal. List the files matching
- X/projects/Ecrypt/*.slice, if there is one for your terminal (e.g.,
- Xvt100.slice), execute it to initialize the necessary shell variables (e.g.,
- Xsource /projects/Ecrypt/vt100.slice).
- X
- X In general an unrecognized keystroke generates a self-insert command.
- XHowever, control characters other than newline and tab are reserved for default
- Xkeystroke commands. To insert a control character, precede it by a C-Q. The
- XC-Q command will create a self-insert command for the next ascii character
- Xreceived from the terminal.
- X
- X The notation C-N will be used to represent pressing the N or n key while
- Xthe control key is held down.
- X
- X4. Getting Started and Getting Out
- X After setting up the shell variables described in the previous section,
- Xyou can invoke the Crypt Breakers' Workbench from any directory by typing:
- X
- X /projects/Ecrypt/cbw fileroot
- X
- XWhere 'fileroot.cipher' is the name of the ciphertext file in the current
- Xdirectory. You do not need to specify the full pathname of the cbw program if
- X/project/Ecrypt is in your shell's search path.
- X
- X To exit the program move the cursor to the bottom window (using the arrow
- Xkeys or C-N or C-X), then type 'q', a space, and a return. The 'q' signifies
- Xthe quit command, the space causes command completion to be invoked (i.e.,
- X'qui ' would work just as well), and the return key causes the command to be
- Xexecuted. If you have changed the decryption window since you last saved your
- Xwork, the program will ask if you really want to quit. Type 'y' if you want to
- Xquit, or any other key to abort the quit command.
- X
- X5. Commands
- X There are two types of commands: keystroke and user commands. Keystroke
- Xcommands are interpreted by the window that currently contains the cursor. For
- Xexample, the up-arrow key generally moves the cursor up by one line, but in the
- Xdecryption-block window, it moves the cursor up two lines. An attempt has been
- Xmade to keep the keystroke commands uniform and emacs-like. The keystroke
- Xcommands will be explained for each window.
- X
- X The user commands can take arguments typed by the user. They are entered
- Xinto the command line via a simple editor and executed when the user types a
- Xreturn. The cursor must be in the user i/o window to type or execute user
- Xcommands. The details of the editor are given in the section on the user i/o
- Xwindow. Each user command is explained in section 7.
- X
- X-------------------------------------------------------------------------------
- X
- X Crypt Breakers' Workbench
- XBlock - 0 Know 14 of 128 wires |Word Match
- X |.n.y
- X@Device[dover]......e[...........o.............A.........@....i. |Andy
- X |envy
- X......................... ...................................... |indy
- X |only
- X....... .................................................xt.r.a. |
- X |
- X..o.......s.........d.s.............e.........t....o.mu......on |
- X |
- X |
- X |
- XProbable word search -- Done |
- X@Device[dover]..t...e[Font.timesroman..].....e.A..i.l....@Sectio |
- Xn..n..................... .r...n......n.ly.....on.....h......... |
- X....... .........;................ons.......e .c.... ....xt.r.a. |
- X..o.......s.........d.s.............e.........t.. .o.mu..c...on |
- X |
- X `----------
- X
- XHelp : F3 enters guess, ^G undoes it.
- XStatus : Command completed.
- XCommand: pwords-from file: mss.words Max dev: 1.2 (try 1.0)
- X
- X-------------------------------------------------------------------------------
- X
- X Figure 5-1: Sample Screen
- X
- X6. Windows
- X The screen is partitioned into seven windows as shown in figure 5-1.
- XAssociated with each window is a keystroke command interpreter and private
- Xstate information. By convention keys like up-arrow, C-D, and delete do
- Xsimilar things in all the windows.
- X
- X There are some keystrokes that have the same effects in all windows, they
- Xare:
- X
- XC-L Redraw the whole screen.
- X
- XC-X, F4 Jump to command input line.
- X
- XC-Q Quote. Insert the following character.
- X
- XC-Z Abort the current command, restore the terminal modes, suspend
- X the program and return to the shell. If the program is
- X restarted, the terminal will be initialized for CBW and the
- X screen redrawn. The command that was active (if any) when the
- X C-Z was received is aborted. Actually this command is invoked
- X when CBW receives a SIGTSTP signal.
- X
- XC-C Restore the terminal modes and kill the CBW process. Actually
- X this command is invoked when CBW receives a SIGINT signal.
- X
- X The following subsections describe the features of the windows starting at
- Xthe top of the screen and working downwards.
- X
- X
- X
- X6.1. Banner window
- X This window contains the program title. Default behavior for arrow keys.
- X
- X
- X
- X6.2. Decryption Block Label window
- X This window contains a single line that describes the block displayed in
- Xthe decryption block storage window. The block number is shown at the left end
- Xof the line. The right hand side of this line displays how much is known about
- Xthe decryption permutation for the current block. This value is expressed in
- Xterms of the number of wires (2-cycles in the permutation) that are known. A
- Xdecryption permutation that maps character A to B also maps B to A, so there
- Xare only 128 wires even though there are 256 possible characters.
- X
- X
- X
- X6.3. Decryption Block Storage window
- X Displays what is known about the plaintext corresponding to a single block
- Xof 256 ciphertext characters. A dot character, which is different from a
- Xperiod character, is shown when the plaintext character is unknown. Other
- Xgraphic characters represent control characters like newline, tab, and
- Xform-feed. If a character decrypts into a byte that has the high bit set
- X(i.e., not an ascii character), it shows as a solid diamond.
- X
- X Most keystrokes are self-insert commands. When a character is inserted,
- Xit replaces the character at the current position, and any deduced characters
- Xare displayed and highlighted (by underlining). The other keystroke command
- Xcharacters are:
- X
- XC-D, DEL Delete character forward, delete backward. This forces a
- X permutation wiring to be removed. It can do unexpected things.
- X Consider a permutation with A wired to B and P wired to
- X Q. Adding a wire from B to P, then removing it with the DEL
- X command does not restore the original AB and PQ wirings.
- X
- XC-G Undo. Backup the permutation to the state it had before the
- X last contiguous sequence of keystrokes. Arrow commands
- X terminate a contiguous sequence of keystrokes. In most cases,
- X undo should be used instead of DEL or C-D.
- X
- XC-T Try-all. Display a list of the ascii characters that could be
- X put in the current cursor position without conflicting with the
- X existing permutation wirings. The list is sorted with the most
- X likely character first (leftmost).
- X
- XC-L Redraws the whole screen. As a side effect this erases the
- X list of characters produced by C-T.
- X
- XF1, C-R Move to the previous block of 256 characters.
- X
- XF2, C-S Advance to next block of 256 characters.
- X
- X
- X
- X6.4. Guess Block Label window
- X Title for the Guess Block Storage window. Default arrow behavior.
- XParameters for guessing commands are displayed in this window.
- X
- X
- X
- X6.5. Guess Block Storage window
- X This window is multiplexed between different strategies for guessing that
- Xa particular plaintext string is at some position in the block. The general
- Xmeaning of the keystroke commands are:
- X
- XF2, C-S Goto next guess.
- X
- XF3, C-A Accept guess, merge it into the current decryption block. This
- X does not automatically advance to the next guess.
- X
- XC-G Undo the merge of a guess. Actually this is identical to the
- X undo in the decryption block storage window, so it will only
- X undo the guess if you have not typed any commands to the
- X decryption window.
- X
- X
- X
- X6.6. Word Lookup
- X This window displays the list of words in a dictionary that match a
- Xparticular pattern. The pattern is specified by the lookup-pattern command
- X(see section 7.4). Only the first 20 or so matches are displayed. The
- Xdictionary file defaults to /usr/dict/words, but the pathname can be set using
- Xthe environment variable DICTIONARY. The dictionary file contains a sorted
- Xlist of words separated by newline characters. Case is ignored.
- X
- X
- X
- X6.7. User I/O window
- X This window consists of three lines: help, status, and command. The help
- Xline changes as the cursor moves between windows. It reminds the user of the
- Xcommands available in the current window. A more elaborate help facility has
- Xnot been implemented. The status line is used to show error and completion
- Xmessages. The cursor cannot be positioned over either the help or status
- Xlines.
- X
- X The command line behaves like a line editor. The editing characters are:
- X
- XC-U Erase the whole line.
- X
- XC-F, C-B Move forward and backward one character.
- X
- XC-D, DEL Delete one character forward or backward.
- X
- XF2, C-S Next-Argument. It searches for the first "%" character in the
- X command line, deletes it and leaves the cursor there. This is
- X used with command templates.
- X
- XSpace Within the first word on the command line, a space character
- X invokes command completion. A completed command string is a
- X template command with argument slots (marked by %) and
- X suggested argument values.
- X
- XReturn Execute command. The cursor can be anywhere within the command
- X line.
- X
- X7. User Commands
- X
- X
- X
- X7.1. quit
- X Exit the program. If any of the permutations have changed since they were
- Xlast saved, the user is asked for confirmation.
- X
- X
- X
- X7.2. save-permutation
- X Associated with each block of the ciphertext is a permutation that tells
- Xhow to decode the known characters. This command saves those permutations.
- XThere is a special permutation, called Zee, that relates the permutations of
- Xsuccessive blocks. The save command also saves Zee.
- X
- X
- X
- X7.3. load-permutations
- X Inverse of save. The ciphertext file is loaded automatically when CBW
- Xstarts, but the permutation file must be loaded explicitly. This command is
- Xused to load previously saved work. Warning: the load command will replace the
- Xcurrent permutations without asking whether you want to save them first.
- X
- X
- X
- X7.4. lookup-pattern
- X Searches a dictionary for words matching a pattern. The dictionary is
- Xspecified by the shell variable DICTIONARY. The pattern is specified as an
- Xargument to the command. Currently, the pattern consists of characters and
- Xperiods (.). The period characters match any one character in a word from the
- Xdictionary. This means that you have to know the length of the word you are
- Xlooking for. The current dictionary does not contain suffixes, so you will
- Xoften need to try a few patterns to find the desired word. There are many ways
- Xto improve this command.
- X
- X
- X
- X7.5. bigram guessing
- X This command uses a statistics based on letter pairs (bigrams) to
- Xcarefully guess at the plaintext. This is the most useful command in CBW and
- Xit represents a significant improvement on the techniques discussed in the
- XReeds and Weinberger paper. This tool works by finding the best position for
- Xguessing, and then trying all 128 ascii characters in that position. For each
- Xof the 128 trials the deduced characters are scored and the trial with the best
- Xscore is accepted if it meets the criteria set by the user. The process
- Xrepeats for the next best position until no positions satisfy the user's cutoff
- Xcriteria.
- X
- X The best position for guessing is the one that produces the most evidence.
- XIt is the position that generates the largest number of deduced characters.
- XPreference is given to positions that are deduced next to an already accepted
- Xcharacter because bigram statistics can be used in these places. An
- Xapproximation to the best position can be identified by examining the
- Xciphertext. For the crypt cipher it is possible to identify all the characters
- Xin the ciphertext that were the output of a particular terminal of the block
- Xrotor. Each of the 128 trial plaintext characters for that position will
- Xgenerate a wiring from that terminal to some other terminal. If the other
- Xterminal is already used, the guess is rejected immediately. However, if the
- Xrotor terminal is free, additional character positions may be deduced because
- Xof the symmetric nature of the rotor (recall that if the rotor maps X to Y then
- Xit also maps Y to X). Thus by examining the ciphertext CBW can set a lower
- Xlimit on the number of characters that will be deduced by guessing in a
- Xparticular position.
- X
- X The bigram command takes two arguments, a cut-off level and a minimum
- Xprobability. The purpose of the cutoff level is to insure that a guess is only
- Xaccepted if the probability of the guess being right is at least some factor
- Xgreater than the probability that the guess is wrong. A cutoff level of 2.0
- Xtells CBW to only accept guesses when the probability of the guess being right
- Xis at least twice as great as the probability that the guess is wrong. Since
- Xall 128 possible guesses are tried, the probability of a guess being wrong is
- Xjust the sum of the probabilities that any other guess is correct.
- X
- X The probability that a guess is correct is based on a statistic that is
- Xthe sum of the logarithm of the expected letter pair frequencies of deduced
- Xcharacters appearing next to the deduced or accepted characters. The mean and
- Xvariance of this statistic is a simple function of the number of characters
- Xdeduced, so it is possible to approximate the probability density distribution
- Xof the statistic with a gaussian distribution. The probability (actually
- Xprobability density) that a guess is correct can be computed from the gaussian
- Xdistribution based on the number of standard deviations that the observed value
- Xof the statistics differs from its expected value.
- X
- X The minimum probability tells CBW to only accept the best guess if its
- Xprobability is higher than some value. The minimum probability comes into play
- Xwhen very few letter pairs are deduced. In those cases it is better to skip
- Xguessing until additional characters have been deduced.
- X
- X This command can be used to automatically deduce about 100 of the 256
- Xpossible positions within a block. It is by far the most useful command in the
- Xworkbench. My usual strategy is to run the command three times on each block,
- Xfirst with a cut-off of 1.5 and a minimum probability of 0.6, then with a
- Xcut-off of 1.2 and a probability of 0.4, and finally with a cut-off of 1.0 and
- Xa probability of 0.15.
- X
- X An essential aspect of this command is that it carefully selects the
- Xpositions where it does guessing. After each guess it selects the position
- Xthat will deduce the maximum number of letters and letter pairs. Without the
- Xcareful searching, it is only slightly more effective than the equivalence
- Xclass command (which is now obsolete).
- X
- X The method for computing the bigram probability is somewhat interesting.
- XRather than having a 128 x 128 entry table, the program uses a 36 x 36 entry
- Xtable with a character mapping table. For example, the character map treats
- Xupper and lower case letters the same, and it treats all left brackets and
- Xparenthesis the same. To compensate for the information lost by treating upper
- Xand lower case letters as the same, the program bases its guess probabilities
- Xon the product (actually products are taken by summing logs) of the monogram
- Xand bigram probabilities for the deduced characters. Compensating for the lost
- Xinformation lead to a 30% increase in the number of correctly guessed
- Xcharacters.
- X
- X
- X
- X7.6. pwords
- X Given a list of words that are likely to be found in the text, this
- Xcommand tries each word in every possible starting position, and accepts a
- Xguess if the score for the deduced characters is within a given number of
- Xstandard deviations of its expected value. The list of words must be stored in
- Xa file, one word per line, using standard C backslashing conventions for
- Xcontrol characters (e.g., "\n" for newline).
- X
- X CBW used to have a command that accepted words from the keyboard, but I
- Xfound that users are more thorough in selecting words if they have to
- Xseparately edit a file. The result is a collection of reusable files that
- Xbecomes a permanent part of your workbench. For example, I have files for mail
- Xheaders, C programs, computer science articles, common short words, and various
- Xtext formatters. Of course in the spirit of a workbench, if you do not like
- Xthis limitation it is easy to add the desired command.
- X
- X
- X
- X7.7. auto-trigram guessing
- X This command is obsolete. Use pword instead.
- X
- X
- X
- X7.8. knit-blocks
- X This command is used to deduce the relationship between successive blocks
- Xof the cipher. That relationship is stored in a permutation called Zee. Given
- Xfour or more partially filled in blocks, the knit command can be used to deduce
- Xinformation about Zee. You can then use the propagate command to transfer what
- Xyou have solved in one block to any other block (see section 7.10). For the
- Xtheory of knitting see the Reeds and Weinberger paper.
- X
- X The knitting processes is not deterministic unless you have completely
- Xsolved four blocks or partially solved more than five blocks. When knitting
- Xblocks k through n, the knit command displays block n+1 in the decryption
- Xwindow and in the guess window it displays the characters that would be deduced
- Xby each knitting guess. You can use the F3 (or C-A) key to accept a guess
- Xand/or the F2 to advance to the next guess.
- X
- X The knit command is intolerant of incorrect decodings of a block. If you
- Xare not sure of the plaintext value of a character (e.g., whether some position
- Xcontains a space or a tab character), it is best to leave character undecoded.
- XIf any character is incorrectly decoded, then the knit command will run for
- Xhours. If the command runs for more than five minutes, abort it with C-Z. A
- Xclever algorithm might avoid this mis-feature.
- X
- X The knit command displays how much of Zee is currently known.
- X
- X
- X
- X7.9. Clear-zee
- X Sets the Zee permutation to a state where no information is known. This
- Xis the only way to recover from a bad knitting.
- X
- X
- X
- X7.10. propagate using Zee
- X If the Zee permutation is partially known, the propagate command can be
- Xused to deduce unknown characters in one block from known characters in another
- Xblock. Its arguments are any two block numbers. The blocks do not have to be
- Xadjacent. The destination block will be displayed in the decryption window
- Xwith the deduced characters highlighted.
- X
- X8. Known Bugs
- X
- X 1. Due to a simple memory allocation strategy, only the first fifteen
- X or so blocks of a file can be examined.
- X
- X 2. CBW can only process full 256 character blocks, which means that it
- X cannot be used to decode very short files.
- X
- X 3. Trigram stats are no longer used, so they should not be loaded.
- X
- X 4. Replacing the knit window without accepting the current guess (by
- X say invoking the propagate command), causes the current knitting
- X guess to be accepted. This bug comes from an oversight in my window
- X package and is a bit of a pain to fix.
- X
- X 5. See the file TODO.txt for a list of suggested enhancements.
- X
- XAcknowledgments
- X The author would like to thank Simson L. Garfinkel, Samuel M. Levitin,
- XClifford Neuman, and Tim Shepard for the ideas and programs they contributed to
- Xthis project. Paul Paloski provided extensive comments on the alpha test
- Xversion of CBW, and John Gilmore enhanced it for portability.
- X
- XI. Graphics Map
- X
- X CBW uses non-ascii symbols to display non-printing characters such as
- Xnewline and tab. Each kind of terminal supports a different set of graphics
- Xcharacters (if any), and even if two terminals support the same graphic (e.g.,
- Xmiddle horizontal bar) they usually represent it by different sequences of
- Xascii characters. CBW handles these differences by using an explicit graphics
- Xsymbol map. The map converts an internal symbol identifier into a string of
- Xascii characters which cause the terminal to display the desired symbol.
- X
- X The graphics map can be set by the user via a shell environment variable.
- XThe map is build in three steps. CBW first looks in the termcap entry for this
- Xterminal for the definitions that describes how to enter and exit the
- Xterminal's standout mode (inverse video) and graphics mode. There must be a
- Xdefinition for standout mode, but the graphics mode fields can be missing.
- XNext, a default graphics map is read from a compiled in string (see
- Xterminal.h). The default map uses standout mode to represent symbols. For
- Xexample, the newline and tab characters are drawn by displaying an 'n' and a
- X't' in standout mode. A complete list of the defaults is given in table I-1.
- X
- X-------------------------------------------------------------------------------
- X
- XGRAPHIC USE
- X\St Tab characters.
- X\SX Non-Ascii character.
- X\Sn Newline character.
- X\Sr Return character.
- X\Sf Form feed character.
- X\SC Other control characters.
- X\S Plaintext character unknown (standout space).
- X\N^ Pseudo underline to highlight char above this one.
- X\N| Vertical line segment.
- X\N- Horizontal line segment.
- X\N` Lower-left corner of box.
- X
- X
- X Table I-1: Default graphic symbols
- X
- X-------------------------------------------------------------------------------
- X
- X The last step of building the graphics map is to read the shell variable
- XGRAPHICSMAP (if it is defined). This variable is formatted like a /etc/termcap
- Xentry. It is a sequence of definitions separated by whitespace (spaces, tabs,
- Xor newlines) or colons. Each definition has a label and a value. The label is
- Xa string terminated by an '=' character. The label associated with each symbol
- Xis given in table I-2. The value is a sequence of characters terminated by a
- Xcolon (or the end of the environment variable string). The first two
- Xcharacters of the value string are special. The first character must be a
- Xbackslash ('\'). The second character specifies the mode that the terminal
- Xshould be in when the remainder of the value string is displayed. That
- Xcharacter must be one of 'N', 'S', or 'G' for normal, standout, or graphic
- Xmode. The combined mode of standout plus graphics cannot be represented (this
- Xcould be fixed in terminal.c). The rest of the value characters can use the
- Xstandard backslash conventions (\n, \r, \t, \f, \\, and \177) with the addition
- Xthat \E will be translated into an escape character (\033).
- X
- X-------------------------------------------------------------------------------
- X
- XLABEL SYMBOL
- Xtb Tab characters.
- Xna Non-Ascii character.
- Xlf Newline character.
- Xcr Return character.
- Xff Form feed character.
- Xcc Other control characters.
- Xuk Plaintext character unknown.
- Xul Pseudo underline to highlight char above this one.
- Xvb Vertical line segment (bar).
- Xhb Horizontal line segment (bar).
- Xll Lower-left corner of box.
- X
- X
- X Table I-2: Symbol labels for graphic map
- X
- X-------------------------------------------------------------------------------
- X
- X The default map string and the h19 graphics map string are listed below to
- Xillustrate the format.
- XDefault Graphics Map String:
- X
- X #define DGRAPHICS "tb=\\St:na=\\SX: lf=\\Sn:cr=\\Sr:\
- X ff=\\Sf:cc=\\SC:uk=\\S :::ul=\\N^:
- X hb=\\N-:vb=\\N|:ll=\\N`:"
- X
- XH19 Graphics Map String:
- X
- X setenv GRAPHICSMAP 'tb=\Gh:lf=\Gk:cr=\Gg:na=\Gi:\
- X ff=\G~:cc=\Gw:uk=\G^:ul=\Gz:\
- X hb=\G'\`':vb=\Ga:ll=\Ge'
- X
- X To make up a new graphics map, you should first find out the range of
- Xsymbols that your terminal can display. Just put your terminal in graphics
- Xmode (see the 'as' and 'ae' definitions in the termcap for your terminal) and
- Xsend it all the ascii character The file /projects/Ecrypt/graphics does this
- Xfor terminal that use \EF and \EG to enter and exit graphics mode (vt100 and
- Xh19).
- X
- XII. Key Map
- X
- X CBW uses a keymap to convert arbitrary sequences of ascii characters into
- Xkeystroke commands. The information in the map comes from the shell
- Xenvironment variable KEYMAP, the termcap entry for the user's terminal, and
- Xfrom a compiled in string that specifies the default map (see terminal.h). The
- Xshell variable overrides the information from the other sources.
- X
- X The termcap entry for the terminal should provide all the information
- Xneeded by CBW. It should not be necessary to use the KEYMAP variable. The
- Xtermcap entry can come from the environment variable TERMCAP, or from the file
- X/etc/termcap based on the value of the variable TERM.
- X
- X The format of the key map environment variable string is the same as the
- Xformat of the graphics map variable except that the first two character of the
- Xvalue field are not treated specially. Each definition in the string binds a
- Xkeystroke command to some sequence of ascii characters. Note that the same
- Xcommand can be bound to two or more sequences. The label portion of the
- Xdefinition identifies the command and the value portion gives the character
- Xsequence. Table II-1 lists the label to use for each keystroke command. Many
- Xof the default bindings come the termcap entry. In those cases, the label for
- Xthe definition in the termcap entry is given. The command labels used in
- XKEYMAP are different from the terminal capability labels used in TERMCAP.
- X
- X-------------------------------------------------------------------------------
- X
- XLABEL COMMAND
- Xup Move cursor up.
- Xdo Move cursor down.
- Xle Move cursor left.
- Xri Move cursor right.
- Xre Redraw screen.
- Xun Undo last guess accepted.
- Xcl Clear command line.
- Xws Word search (not fully implemented).
- Xdf Delete current character and move forward.
- Xdb Move left and delete that character.
- Xpr Previous block or guess.
- Xne Next block or guess.
- Xac Accept guess.
- Xex Execute command line or insert newline.
- Xta Try all characters in this position.
- Xjc Jump to command line.
- X
- X
- X Table II-1: Command labels for key map
- X
- X-------------------------------------------------------------------------------
- X
- X Several termcap definitions are required by CBW and several others are
- Xused if they are present. CBW will print a message and exit if one of the
- Xrequired definitions is missing. Table II-2 list all the definitions used by
- XCBW.
- X
- X-------------------------------------------------------------------------------
- X
- XLABEL USE
- Xis Terminal initialization string.
- Xce Erase to end of line.
- Xcd Erase to end of screen.
- Xcl Erase whole screen.
- Xcm Cursor motion.
- Xas Start graphics mode.
- Xae End graphics mode.
- Xso Start standout mode.
- Xse End standout mode.
- Xks Start send keypad escapes.
- Xke End send keypad escapes.
- Xk1 The f1 key.
- Xk2 The f2 key.
- Xk3 The f3 key.
- Xk4 The f4 key.
- Xku Up arrow.
- Xkd Down arrow.
- Xkl Left arrow.
- Xkr Right arrow.
- X
- X
- X Table II-2: TERMCAP definitions used by CBW
- X
- X-------------------------------------------------------------------------------
- X
- XIII. Command Summary
- X
- X
- XKEYSTROKE COMMAND
- X
- XC-L Redraw the whole screen. As a side effect this erases the list
- X of characters produced by C-T.
- X
- XC-X, F4 Jump to command input line.
- X
- XC-Q Quote. Insert the following character.
- X
- XC-Z Abort the current command, restore the terminal modes, suspend
- X the program and return to the shell. If the program is
- X restarted, the terminal will be initialized for CBW and the
- X screen redrawn. The command that was active (if any) when the
- X C-Z was received is aborted. Actually this command is invoked
- X when CBW receives a SIGTSTP signal.
- X
- XC-C Restore the terminal modes and kill the CBW process. Actually
- X this command is invoked when CBW receives a SIGINT signal.
- X
- XC-D, DEL Delete character forward, delete backward. This forces a
- X permutation wiring to be removed. It can do unexpected things.
- X Consider a permutation with A wired to B and P wired to
- X Q. Adding a wire from B to P, then removing it with the DEL
- X command does not restore the original AB and PQ wirings.
- X
- XC-G Undo. Backup the permutation to the state it had before the
- X last contiguous sequence of keystrokes. Arrow commands
- X terminate a sequence. In most cases, undo should be used
- X instead of DEL or C-D. The cursor must be in either the guess
- X block or the decryption block window.
- X
- XC-T Try-all. Display a list of the ascii characters that could be
- X put in the current cursor position without conflicting with the
- X existing permutation wirings. The list is sorted with the most
- X likely character first (leftmost). The cursor must be in the
- X decryption block window.
- X
- XF1, C-R Move to the previous block of 256 characters. Decryption block
- X window only.
- X
- XF2, C-S Advance to next block of 256 characters. Decryption block
- X window only.
- X
- XF2, C-S Goto next guess. Guess block window only.
- X
- XF3, C-A Accept guess, merge it into the current decryption block. This
- X does not automatically advance to the next guess. Guess block
- X window only.
- X
- XC-F, C-B Move forward and backward one character.
- X
- XC-D, DEL Delete one character forward or backward.
- X
- XF2, C-S Next-Argument. It searches for the first "%" character in the
- X command line, deletes it and leaves the cursor there. This is
- X used with command templates.
- X
- XSpace Within the first word on the command line, a space character
- X invokes command completion. A completed command string is a
- X template command with argument slots (marked by %) and
- X suggested argument values.
- X
- XReturn Execute command. The cursor can be anywhere within the command
- X line.
- X
- X
- X
- X-------------------------------------------------------------------------------
- X
- X USER COMMANDS
- X
- X
- Xquit-program permanently
- X
- Xauto-trigram max_dev: % min_total_chars: % min_wire_chars: %
- X
- Xknitting using blocks from: % to: % Min show count: %
- X
- Xlookup-pattern: % in dictionary
- X
- Xequivalence-class guess, use accept level: % (try 2.0)
- X
- Xpwords-from file: % Max dev: % (try 1.0)
- X
- Xload-permutations
- X
- Xsave-permutations
- X
- Xclear-zee permutation
- X
- Xpropagate-info from: % to: % using Zee
- X
- Xbigram-guess level: % (2.0), min_prob: % (0.15)
- X
- XIV. Tutorial
- X
- X The following is a step by step sequence of commands to compile and
- Xexercise the Crypt Breakers Workbench. It demonstrates how easily crypt files
- Xcan be broken.
- X
- X 1. Edit stats.slice to set the name of the directory that contains the
- X statistics files. Statistics for scribe documents are included with
- X the source files.
- X
- X The stats.slice file also defines the location of the dictionary
- X used by the lookup-pattern command. The default dictionary is
- X /usr/dict/words. The dictionary is just a list of words, one per
- X line. Case does not matter.
- X
- X 2. Execute 'source stats.slice' to initialize the necessary shell
- X variables.
- X
- X 3. If there is a .slice file for your terminal type (e.g., vt100.slice,
- X or h19.slice), execute source on that file. This initializes the
- X graphics map and key map.
- X
- X 4. Print out cbw.doc, so you can read it after you have decided that
- X you can't figure out how the program works.
- X
- X 5. Copy test3.perm and .cipher to foo.perm and foo.cipher. The .txt
- X files contain the original plaintext.
- X
- X 6. Execute 'cbw foo'.
- X
- X 7. The cursor will on the command line. Use the arrow keys (or C-P,
- X C-N, C-F, C-B) to move the cursor to the upper lefthand position of
- X the decryption window. Try typing '@Device[Dover]'. Notice that
- X most of the characters you type deduced other characters in the
- X block.
- X
- X 8. The 'D' in 'Dover' is wrong. Using the arrow keys, position the
- X cursor over the 'D' and type 'd'.
- X
- X 9. Advance to the position after the ']' and type C-T. A list of
- X possible characters for this position will be displayed. The list
- X is sorted with the most likely character on the left. Notice that
- X many characters are not possible because they would deduce non-ascii
- X characters elsewhere in the block, or they would conflict with
- X previously accepted guesses.
- X
- X Try guessing tab, comma and linefeed for the character after the
- X ']'. Use C-G to undo each guess. Delete and C-D do not restore the
- X old state, they just erase the wiring that was deduced by a
- X particular character.
- X
- X 10. Move the cursor down to the command line. You can use emacs cursor
- X characters (C-N, C-P, C-F, C-B) or the arrow keys. Unfortunately,
- X C-U does not work as in emacs. The C-X key or F4 will jump directly
- X to the command line.
- X
- X 11. Type 'pw '. The space will cause command completion for the
- X probable-word guessing command. Type F2 (or C-S) to advance to the
- X first argument, and enter the file name 'mss.words'. That file
- X contains a list of keywords used by the Scribe (Finalword) text
- X formatter. Press F2 to advance to the second argument, which
- X specifies a cut-off level for automatically accepting guesses. The
- X level is the maximum number of standard deviations that the scoring
- X function can be away from its expected value. Enter 1.2, and press
- X return to invoke the command.
- X
- X 12. A partially filled in block will appear in the guessing window. To
- X accept the result of this command, press F3 (or C-A).
- X
- X 13. Try the pword guess command again with a level of 3. To do this,
- X just move to the command line, change the 1.2 to a 3, and press
- X return. Again F3 accepts the guess. If some guesses look wrong
- X (such as the 'F' on the second line under the '[Article]'), you can
- X correct them using the editor in the decryption block window.
- X
- X 14. Advance to block 1 of the file by moving the cursor to the
- X decryption window and pressing F2 (or C-S). F1 (or C-R) moves back
- X one block, F2 moves ahead one block.
- X
- X 15. The second block is likely to be plain english with few scribe
- X commands. Move to the command window, type C-U to erase the line
- X and type 'bi ' to setup the bigram guessing command. Try an
- X acceptance level of 1.0 and a minimum probability of 0.6. Type
- X return to invoke the command.
- X
- X 16. After a short wait (~15 seconds), a partial block will appear.
- X Accept the guess with the F3 key in the guessing window.
- X
- X 17. Try looking up a pattern in the dictionary. In the command window
- X type 'look ', use F2 to advance to the pattern, and type in the
- X pattern '....llit.', and press return. This will match against the
- X word 'satellite' if it is in you site's dictionary.
- X
- X 18. One could go on like this, but let's skip ahead by loading in a
- X previously saved state. Invoke the load command (it loads the file
- X foo.perm, just as save dumps to foo.perm (making this command take a
- X filename is a good implementation exercise)). Type C-U, 'load ',
- X and return. Notice that all the work so far is replaced by the
- X information in the .perm file. This can be considered a feature.
- X
- X 19. Use the F1 and F2 keys in the decryption window to view the blocks
- X that have been solved. Notice that a fully solved block does not
- X specify all the wirings of the block key (permutation). Typically
- X only 105 of the 128 wires are used.
- X
- X 20. Lets try deducing the inter-block relationship (zee). Execute the
- X clear-zee command.
- X
- X 21. Execute knit blocks 0 through 3 with a min show count of 20. This
- X means that the program should only show you guesses that deduce 20
- X or more wirings of the zee permutation. Press return to invoke this
- X guessing strategy. The cursor will move to the guessing window.
- X Press F2 to start the first round of guessing.
- X
- X The running time of the knit command is exponential in the number of
- X blocks knitted, and it will run for a very long time if any of the
- X blocks are decrypted incorrectly. This means that it is better to
- X leave a position blank than to guess at it.
- X
- X 22. The program moves to block 4 and shows you the characters in block 4
- X that would be deduced from block 3 given the deduced wirings of zee.
- X If these look reasonable, press F3 to accept the guess, and press F2
- X to try the next guess. To reject a guess, press F2 without pressing
- X F3.
- X
- X 23. Now that part of zee is known, try propagating the settings of block
- X 1 into block 0 using zee. The propagate command will do this. Also
- X try propagating blocks 2, 3, and 4 to zero.
- X
- X Notice that the number of known wires can increase without deducing
- X additional characters in the block.
- X
- X 24. There should be a command that propagates information between groups
- X of blocks, but for now you must do this one block at a time. After
- X propagating block 1 - 4 to block zero, and block zero to blocks 1 -
- X 4, et cetera, try the knit command again.
- X
- X 25. Propagate block 4 to 5 to provide a framework to evaluate new
- X guesses.
- X
- X 26. Knit block 0 through 4 with a minimum show level of 2. You may want
- X to skip accepting guesses that do not deduce any characters. Repeat
- X this process with a show level of 1.
- X
- X 27. The program should now know all 256 wirings of zee. Repeat the
- X process of propagating information between blocks until all 128
- X wires of the block zero are known.
- X
- X 28. Save your work with the save-permutations command (on the command
- X line type 'sa ' and press return). This writes the file foo.perm.
- X
- X 29. Exit the program with the quit command.
- X
- X 30. Copy foo.perm to zeecode.perm.
- X
- X 31. Execute 'zeecode < foo.cipher | more '. This program reads CBW's
- X save file to find the permutation for block zero and the Zee
- X permutation that describes how the remaining block keys are
- X generated. Using this information it decodes standard input and
- X writes on standard output.
- X
- X 32. That's all.
- X
- X Table of Contents
- XOverview 2
- X1. Introduction to the Workbench 2
- X2. Key Space Attack 2
- X3. Files, Terminals and Shell Variables 2
- X 3.1. Terminal compatibility 2
- X4. Getting Started and Getting Out 2
- X5. Commands 2
- X6. Windows 4
- X 6.1. Banner window 4
- X 6.2. Decryption Block Label window 4
- X 6.3. Decryption Block Storage window 4
- X 6.4. Guess Block Label window 4
- X 6.5. Guess Block Storage window 4
- X 6.6. Word Lookup 4
- X 6.7. User I/O window 4
- X7. User Commands 4
- X 7.1. quit 4
- X 7.2. save-permutation 4
- X 7.3. load-permutations 4
- X 7.4. lookup-pattern 4
- X 7.5. bigram guessing 4
- X 7.6. pwords 5
- X 7.7. auto-trigram guessing 5
- X 7.8. knit-blocks 5
- X 7.9. Clear-zee 5
- X 7.10. propagate using Zee 5
- X8. Known Bugs 5
- XAcknowledgments 6
- XI. Graphics Map 7
- XII. Key Map 8
- XIII. Command Summary 9
- XIV. Tutorial 10
- X
- X List of Figures
- XFigure 5-1: Sample Screen 3
- X
- X List of Tables
- XTable I-1: Default graphic symbols 7
- XTable I-2: Symbol labels for graphic map 7
- XTable II-1: Command labels for key map 8
- XTable II-2: TERMCAP definitions used by CBW 8
- END_OF_cbw.doc
- if test 51998 -ne `wc -c <cbw.doc`; then
- echo shar: \"cbw.doc\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- echo shar: End of archive 11 \(of 11\).
- cp /dev/null ark11isdone
- MISSING=""
- for I in 1 2 3 4 5 6 7 8 9 10 11 ; do
- if test ! -f ark${I}isdone ; then
- MISSING="${MISSING} ${I}"
- fi
- done
- if test "${MISSING}" = "" ; then
- echo You have unpacked all 11 archives.
- rm -f ark[1-9]isdone ark[1-9][0-9]isdone
- else
- echo You still need to unpack the following archives:
- echo " " ${MISSING}
- fi
- ## End of shell archive.
- exit 0
-